"""动态规划"""
class Solution:
    #最小路径和
    def min_path_sum(self,grid:[[]]):
        for i in range (len(grid)): #行长
            for j in range (len(grid[0])):  #列长
                #第一列元素合并来源：上
                if j==0 and i!=0 :
                    grid[i][j]+=grid[i-1][j]
                #第一行元素合并来源：左
                elif j!=0 and i == 0:
                    grid[i][j]+=grid[i][j-1]
                #中间元素合并来源：上与左取较小
                elif j!= 0 and i!= 0:
                    grid[i][j]+=min(grid[i-1][j],grid[i][j-1])
        return grid[len(grid)-1][len(grid[0])-1]


sol1 =Solution()
print(sol1.min_path_sum([[1,3,1],[1,5,1],[4,2,1]]))

